package Day_002_T738;

/**
 * @author XIAOLIANG
 * @ClassName T738.java
 * @Description TODO
 * @createTime 2020年12月15日 20:37:00
 * 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
 *
 * （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
 *
 * 示例 1:
 *
 * 输入: N = 10
 * 输出: 9
 * 示例 2:
 *
 * 输入: N = 1234
 * 输出: 1234
 * 示例 3:
 *
 * 输入: N = 332
 * 输出: 299
 * 说明: N 是在 [0, 10^9] 范围内的一个整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/monotone-increasing-digits
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class T738 {

	public int monotoneIncreasingDigits(int N) {

		//1 将数字转换成字符数组
		String s = String.valueOf(N);
		char[] chars = s.toCharArray();

		//2从右往左扫描字符数组  每次拿出两个  如果右边的小于左边 左边的数 减一 右边所有的数 变为9
//		如果是从左往右 332  会变成329 改变之后又会造成左边的数大于右边的数
		int flag= chars.length-1;

		for (int i = flag; i>0;i--) {
			//发现左边的数 大于右边的数  记录当前的坐标 将左边的数减一 并结束循环
//			此处不需要考虑0 的问题 比如  100009  ------>   从右向左 当第一位减一  后面又会重新置为9
			if (chars[i]<chars[i-1]){
				flag = i-1;
				chars[i-1]--;
			}
			
		};

		//将后面所有的数置为9

		for (int j = flag+1; j < chars.length ; j++) {
			chars[j] = '9';
		}



		return Integer.parseInt(new String(chars));

	}



}
